#include <vector>
#include <unordered_map>
#include <string>
using namespace std;
/*
 * @lc app=leetcode.cn id=149 lang=cpp
 *
 * [149] 直线上最多的点数
 */

// @lc code=start
class Solution {
public:
    // 没啥意思的提
    int maxPoints(vector<vector<int>>& points) {
        int res = 0;
        for (int i = 0; i < points.size(); i++) {
            unordered_map<string, int> record;
            vector<int> p1 = points[i];
            for (int j = i + 1; j < points.size(); j++) {
                vector<int> p2 = points[j];
                int dx = p1[0] - p2[0], dy = p1[1] - p2[1];
                int common = gcd(dx, dy); 
                string key = to_string(dx / common) + "_" + to_string(dy / common);
                record[key]++;
                res = max(res, record[key]);
            }
        }
        return res + 1;
    }

    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
};
// @lc code=end

